package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class integerBreak_ {
  public static void main(String[] args) {
    System.out.println(integerBreak(10));
  }

  // 1. dp[i]表示数字i被拆分后得到的乘积最大值为dp[i]
  // 2. 递推公式: i被拆为2个以上的数时: dp[i] = j * dp[i - j]; i被拆为2个数 dp[i] = j * (i - j);
  // 3. 初始化: dp[0] = 0,dp[1] = 0,dp[2] = 1;
  // 4. 遍历顺序: i = 3 i <= n i++{j = 1 j < i j++} 将i分为j
  public static int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    for (int i = 3 ; i <= n ; i++){
      for (int j = 1 ; j < i ; j++){
        // 这里为什么有dp[i]比较, 因为在拆分时, i被拆为各种j, 选一个j乘积最大的
        // 例如4被拆为1,3;1,1,2;1,1,1,1
        // 和dp[i]取max目的是为了 找到1,3;1,1,2;1,1,1,1四种拆分乘积最大的一种
        dp[i] = Math.max(Math.max(j * (i - j),j * dp[i - j]),dp[i]);
      }
    }
    return dp[n];
  }
}
